#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>

using namespace std;

vector<int> ret;
vector<int> index;
int tmpnums[100010];
int tmpindex[100010];

void mergesort(vector<int>& ret, vector<int>& index, vector<int>& nums, int left, int right);

vector<int> countSmaller(vector<int>& nums) {
    int n = nums.size();
    ret.resize(n);
    index.resize(n);
    for (int i = 0; i < n; ++i) index[i] = i;
    mergesort(ret, index, nums, 0, n - 1);
    return ret;
}
void mergesort(vector<int>& ret, vector<int>& index, vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int mid = left + ((right - left) >> 1);

    mergesort(ret, index, nums, left, mid);
    mergesort(ret, index, nums, mid + 1, right);

    int cur1 = left, cur2 = mid + 1, i = 0;
    while (cur1 <= mid && cur2 <= right) {
        if (nums[cur2] >= nums[cur1]) {
            tmpindex[i] = index[cur2];
            tmpnums[i++] = nums[cur2++];
        }
        else {
            ret[index[cur1]] += right - cur2 + 1;
            tmpindex[i] = index[cur1];
            tmpnums[i++] = nums[cur1++];
        }
    }
    while (cur1 <= mid) tmpindex[i] = index[cur1], tmpnums[i++] = nums[cur1++];
    while (cur2 <= right) tmpindex[i] = index[cur2], tmpnums[i++] = nums[cur2++];

    for (int j = left; j <= right; ++j) index[j] = tmpindex[j - left], nums[j] = tmpnums[j - left];
}


int main() {
    vector<int> nums{ 3,4,5,2,1 };
    vector<int> ret =  countSmaller(nums);
    for (auto e : nums) cout << e << " ";
    cout << endl;
    for (auto e : ret) cout << e << " ";
    return 0;
}